1. Field of the Invention
The present invention relates to techniques for avoiding bus deadlock and, in particular, to bus logic, an apparatus and a method for preventing bus deadlock situations occurring.
2. Description of the Prior Art
The problem of bus deadlock is known. A bus deadlock will typically occur when the configuration of the bus prevents logic units coupled thereto from performing or completing data transfers. When the deadlock occurs it is often very difficult to restore the bus to a normal operating state. Therefore, when deadlock occurs it is generally required that the configuration of the bus is reset, which will also typically impact on the configuration and operation of logic units coupled thereto. Hence, these logic units may also need to be reset to enable the required data transfers to be performed or completed. Accordingly, it will be appreciated that bus deadlock can have a devastating impact on the performance of a data processing apparatus.
A known bus arrangement which can exhibit deadlock is shown in FIG. 1. In this arrangement there are two master logic units (master 1 and master 2) which can initiate data transfers with either of two slave logic units (slave A and slave B). Bus interconnect 10 comprises a number of multiplexers 50, 80 and demultiplexers 70, 60. The multiplexers 50, 80 are controlled by an associated FIFO 55, 85 which ensures that read data is returned to the master in the same order as the read addresses were issued. The demultiplexers 70, 60 are controlled by an associated decoder 65, 75 which selects the correct destination based on an identifier which accompanies the read data.
In many situations, this arrangement satisfactory enables data transfers to be performed between the masters and slaves, as required. However, a situation can occur when the bus interconnect 10 is configured such that a deadlock occurs. Such a deadlock manifests when no data transfers can occur because each data transfer is dependent on another, and none of those data transfers can complete.
To illustrate a simple deadlock consider the following sequence of data transfers: firstly, master 1 sends a read address to slave A, indicating that it requires read data; then master 1 sends a read address to slave B. The interconnect must ensure that the data is returned to the master in the correct order, from slave A then slave B. Before any data is transmitted, master 2 sends a read address to slave B, then one to slave A. Once again, the interconnect must ensure that the read data is returned in the address order, slave B then slave A. At this point, the interconnect has the state indicated in FIG. 1 with FIFOs 55 and 85 driving the read data multiplexors 50 and 80 to select the correct slave for that master.
Whilst it would be appreciated that in the normal course of events the bus interconnect 10 will enable the data transfers to occur in the required sequence, a problem exists in that it is often the case that at least one of the slaves is operable to reorder the sequence in which data is to be returned. This reordering of the returned data can occur for many different reasons. For example, if the slave is processing multiple data requests and an earlier data request is to a slow memory whilst a later request is to a faster memory, then it may be that the slave is able to provide the data for the later request prior to the early request. Such reordering of data can result in a deadlock occurring.
To illustrate how this can result in a deadlock, consider for example that slave A is able to reorder read data and provides the data requested by master 2 before the data requested by master 1. However, multiplexer 80 is currently configured to receive data from Slave B, which is trying to send data to Master 1, which in turn needs data from Slave A. Accordingly, none of the data transfers can occur and the bus interconnect 10 is said to be in a deadlock state. As mentioned above, one known technique to overcome this problem is to reset the configuration of the bus interconnect 10. However, it will be appreciated that even for this simple arrangement, resetting the bus interconnect 10 is a significant task since many data transfers may be queued and it may not be clear which event caused the deadlock to occur. Hence, such deadlock situations are normally resolved by way of a hard reset of the bus interconnect 10, and of the associated masters and slaves. It will appreciated that such resetting is undesirable since it can significantly impact on the performance of the overall system and may be potentially disastrous in any safety critical applications.
Accordingly, it is desired to provide an improved technique for performing data transfers over a bus which prevents bus deadlock situations occurring.